home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / ddjcompr / hstest / src / huffp.c < prev    next >
C/C++ Source or Header  |  1991-04-28  |  20KB  |  888 lines
  1. #include "stdio.h"
  2. #include "fcntl.h"
  3. #include "tomlib.h"
  4. #include "setjmp.h"
  5.  
  6. #include "pq.h"
  7. #include "huffman.h"
  8. #include "pack.h"
  9.  
  10. #define STATIC
  11.  
  12. #define MIN_LENGTH        3        /* minimum to be compressed */
  13. #define MAXCODELENGTH 0x0f
  14. #define SENDLEN        0xfff        /* MUST BE 00001111111 */
  15.  
  16. typedef unsigned char uchar;
  17. typedef unsigned short uint;
  18.  
  19.  
  20. jmp_buf bit_to_long = {0};
  21.  
  22.  
  23. void *ck_alloc(unsigned int len)
  24. {
  25.     void *calloc(),*s;
  26.     if ((s = calloc(len,1)) == NULL)
  27.         panic("can't allocate memory");
  28. }
  29.  
  30. STATIC uint ln2(register uint charset)
  31. {
  32.     register int ln;
  33.     for (ln = 0; charset > 1; charset >>= 1)
  34.         ln++;
  35.     return ln;
  36. }
  37.  
  38. typedef struct huff_code {
  39.         unsigned bitcode;
  40.         uchar     bitcnt;
  41.         } huff_code;
  42.  
  43. typedef struct huff_icode {
  44.         uchar bitcode;
  45.         uchar bitcnt;
  46.         } huff_icode;
  47.  
  48.  
  49. STATIC void    swap_ptr(huff_tab **c1,huff_tab **c2);
  50. STATIC int  cmp_ptr (huff_tab **c1,huff_tab **c2);
  51. STATIC void _fastcall addbit(huff_tab *cpt);
  52. STATIC void _fastcall bit_write(register unsigned value,register int length);
  53. STATIC uint _fastcall bit_read(register int length);
  54. STATIC uint _fastcall huff_read(huff_icode *icode,int maxbit);
  55. /**
  56. *** generate Huffman codes for every character 
  57. **/
  58.  
  59. panic(char *s)
  60. {
  61.     printf("%s\n",s);
  62.     exit(1);
  63. }
  64.  
  65. STATIC void swap_ptr(huff_tab **c1,huff_tab **c2)
  66. {
  67.     void *tmp;
  68.     tmp = *c1;
  69.     *c1 = *c2;
  70.     *c2 = tmp;
  71. }
  72. STATIC int cmp_ptr(huff_tab **c1,huff_tab **c2)
  73. {
  74.     return (*c2)->count-(*c1)->count;
  75. }
  76.  
  77.  
  78. STATIC int current_max_bit;
  79.  
  80. STATIC void _fastcall addbit(register huff_tab *cpt)
  81. {
  82.     while (cpt) {
  83.         addbit(cpt->lpt);
  84.         if (++cpt->bitcnt > current_max_bit)
  85.             longjmp(bit_to_long,1);
  86.         cpt = cpt->rpt;                            // faster then recursion
  87.         }
  88. }
  89.  
  90. //**********************************************************************
  91. // generate from huff_tab a field bitlength which holds the best bitlength
  92. // for each character. allthough it would be possible to generate codes
  93. // at the same time this has been avoided to make it easier usable when
  94. // the data are read back
  95. //**********************************************************************
  96.  
  97.  
  98. STATIC int gen_length(uchar *bitlength,huff_tab *hufftab,
  99.                                                     int charset,int maxbit)
  100. {
  101.     PQ *pq;
  102.     huff_tab *cpt,*cpt1,*cpt2,*cpt3;
  103.     register int i;
  104.     long bsum;
  105.     int multiply ;
  106.     int anzcodes;
  107.  
  108.     current_max_bit = maxbit;            // we will not allow a longer table
  109.                                         // so the table is made more "flat"
  110.     if (setjmp(bit_to_long))
  111.         {
  112.         free(pq);
  113.         for (i=charset,cpt=hufftab;--i >= 0;cpt++)
  114.             {
  115.             if (cpt->count > 1)
  116.                 cpt->count /= 2;
  117.             cpt->bitcnt = 0;
  118.             cpt->lpt = cpt->rpt = NULL;
  119.             }
  120.         multiply *= 2;
  121.         }
  122.     else
  123.         multiply = 1;
  124.  
  125.     pq = pq_create(charset,sizeof(huff_tab*),cmp_ptr,swap_ptr,(void*)0);
  126.  
  127.     for (anzcodes = 0,i=charset,cpt=hufftab;--i >= 0;cpt++)
  128.         if (cpt->count)
  129.             {
  130.               pq_ins(pq,&cpt);
  131.             anzcodes++;
  132.             }
  133.  
  134.     if (anzcodes == 1)                // the buffer is degenerated
  135.         {                            // so we must set one code
  136.         pq_del(pq,&cpt1);
  137.         addbit(cpt1);
  138.         }
  139.     else {
  140.  
  141.         cpt3 = hufftab+charset;
  142.         while(pq_del(pq,&cpt1) && pq_del(pq,&cpt2))
  143.              {
  144.             addbit(cpt1);
  145.             addbit(cpt2);
  146.             cpt3->lpt = cpt1;
  147.             cpt3->rpt = cpt2;
  148.             cpt3->bitcnt = cpt2->bitcnt;
  149.             cpt3->count= cpt1->count+cpt2->count;
  150.             pq_ins(pq,&cpt3);
  151.             cpt3++;
  152.               }
  153.         }
  154.  
  155.     for (bsum = 0,i=charset,cpt=hufftab; i ;cpt++,--i)
  156.         {
  157.         bsum += cpt->bitcnt*cpt->count;
  158.         *bitlength++ = cpt->bitcnt;
  159.         }
  160.  
  161.     free(pq);
  162.     return (int)((bsum+15)/8*multiply);
  163. }
  164.  
  165. //**********************************************************************
  166. // generate from huff_tab a field bitlength which holds the best bitlength
  167. // for each character. allthough it would be possible to generate codes
  168. // at the same time this has been avoided to make it easier usable when
  169. // the data are read back
  170. //**********************************************************************
  171.  
  172.  
  173. STATIC int gen_code(huff_code *hufftab,uchar *bitlength,int charset)
  174. {
  175.     register int loop,bitval,bitmask,first,lastcode,length;
  176.     for (loop = 0; loop < charset;loop++)
  177.         {
  178.         hufftab[loop].bitcnt  = bitlength[loop];
  179.         hufftab[loop].bitcode = 0xffff;
  180.         }
  181.  
  182.     lastcode = 0;
  183.     bitmask  = 1;
  184.     first = 1;
  185.  
  186.     for (length = 16; length >= 1; length--,bitmask <<= 1)
  187.         for (loop = 0; loop < charset;loop++)
  188.             {
  189.             if (hufftab[loop].bitcnt  == length)
  190.                 {
  191.                 if (!first)
  192.                     {
  193.                     lastcode += bitmask;
  194.                     }
  195.                 first = 0;
  196.                 hufftab[loop].bitcode = lastcode & ~(0xffff >> length);
  197.                 }
  198.             }
  199. }
  200.     
  201.  
  202.  
  203.  
  204. STATIC gen_invtab(huff_icode *inv,huff_code *tab,int charset,int max_bit)
  205. {
  206.     register int loop,ival,ianz,bitcnt;
  207.  
  208.     for (loop = 0; loop < charset; loop++)
  209.         {
  210.         ival = tab[loop].bitcode >> (16-max_bit);
  211.         if ((bitcnt = tab[loop].bitcnt) == 0)
  212.             continue;
  213.         ianz = 1 << (max_bit-tab[loop].bitcnt);
  214.         for ( ; --ianz >= 0;ival++)
  215.             {
  216.             inv[ival].bitcode = loop;
  217.             inv[ival].bitcnt  = bitcnt;
  218.             }
  219.         }
  220. }
  221.  
  222. #define HIGH_BIT 16
  223. unsigned short bit_value = 0;
  224. unsigned short far *bit_ptr = NULL;
  225. unsigned int   bit_drin= 0;
  226.  
  227. #define dbrange(x) 0            // ((x) >= 0x1b0 && (x) <= 0x1d0)
  228.  
  229. STATIC void bit_flush(void)
  230. {
  231.     if (bit_drin)
  232.         *bit_ptr++ = bit_value;
  233. }
  234.  
  235. STATIC void bit_init(void far *ptr)
  236. {
  237.     bit_ptr  = ptr;
  238.     bit_drin = 0;
  239.     bit_value = 0;
  240. }
  241.  
  242.  
  243. STATIC void _fastcall bit_write(register unsigned value,register int length)        
  244. {
  245.     int fits = HIGH_BIT - bit_drin;
  246.  
  247.     if (length <= fits)
  248.         {
  249.         *bit_ptr |= value >> bit_drin;
  250.         if (length == fits)
  251.             {
  252.             *bit_ptr++ = bit_value | (value >> bit_drin);
  253.             bit_drin  = 0;
  254.             bit_value = 0;
  255.             }
  256.         else 
  257.             {
  258.             bit_value |= value >> bit_drin;
  259.             bit_drin+=length;
  260.             }
  261.         }
  262.     else
  263.         {
  264.         *bit_ptr++ = bit_value | (value >> HIGH_BIT-fits);
  265.         bit_value  = value <<= fits;
  266.         bit_drin = length-fits;
  267.         }
  268. }
  269. STATIC uint _fastcall bit_read(register int maxbit)
  270. {
  271.     register unsigned value;
  272.  
  273.     if (maxbit <= HIGH_BIT-bit_drin)
  274.         {
  275.         value = (*bit_ptr << bit_drin) >> (HIGH_BIT-maxbit);
  276.         }
  277.     else {
  278.         value = ((bit_ptr[0] << bit_drin) | (bit_ptr[1] >> (HIGH_BIT-bit_drin))) 
  279.                 >> (HIGH_BIT-maxbit);
  280.         }        
  281.  
  282.     if ((bit_drin += maxbit) >= HIGH_BIT)
  283.         bit_drin -= HIGH_BIT,bit_ptr++;
  284.  
  285.     return value;
  286. }    
  287.  
  288. STATIC uint _fastcall huff_read(huff_icode *icode,int maxbit)
  289. {
  290.     register int loop,value;unsigned int lmask,*lptr;
  291.  
  292.     if (maxbit <= HIGH_BIT-bit_drin)
  293.         {
  294.         value = (*bit_ptr << bit_drin) >> (HIGH_BIT-maxbit);
  295.         }
  296.     else {
  297.         value = ((bit_ptr[0] << bit_drin) | (bit_ptr[1] >> (HIGH_BIT-bit_drin))) 
  298.                 >> (HIGH_BIT-maxbit);
  299.         }        
  300.  
  301.     if ((bit_drin += icode[value].bitcnt) >= HIGH_BIT)
  302.         bit_drin -= HIGH_BIT,bit_ptr++;
  303.  
  304.     return icode[value].bitcode;
  305. }    
  306.  
  307. //****************************************************************************
  308. // reading / writing characterset bitcounts
  309. //  0) write no characterset at all
  310. //  1) write number of characters (4 Bits) with number of bits (4 Bits) PKZIP
  311. //  2) write for each character number of bits (4 Bits)
  312. //  3) set bitval to 0;
  313. //            while (bitval < bitcnt) write (0x10,2)
  314. //            while (bitval > bitcnt) write (0x11,2)
  315. //            write (0,1)
  316. //  4) if (bitval OK) write (0,1)
  317. //       else write (1,1),write (number of Bits,4)
  318. //****************************************************************************
  319.  
  320. unsigned bit_write_method = 0;
  321.  
  322.  
  323. int write_cnt0(register uchar *bitlength,int charset,uint test)
  324. {
  325.     return 0;
  326. }
  327.  
  328. int read_cnt0(register uchar *bitlength,int charset)
  329. {
  330.     int mask,bits;
  331.     for (bits = 0,mask = 1;mask < charset ; mask <<= 1)
  332.         bits++;
  333.     memset(bitlength,bits,charset);
  334. }
  335. //****************************************************************************
  336.  
  337. int write_cnt1(register uchar *bitlength,int charset,uint test)
  338. {
  339.     register int needed,loop,id;
  340.  
  341.     for (id = 0,loop=0,needed=0; loop < charset;loop++,bitlength++)
  342.         {
  343.         if (bitlength[0] == bitlength[1] && id < 15 && loop < charset-1)
  344.             id++;
  345.         else
  346.             {
  347.             if (test) bit_write(((bitlength[0] << 4) | id) << 8,8);
  348.             id = 0;
  349.             needed++;
  350.             }
  351.         }
  352.     return needed;
  353. }
  354.  
  355. read_cnt1(uchar *bitlength,int charset)
  356. {
  357.     register int loop,id,val;
  358.  
  359.     do     {
  360.         id  = bit_read(8);
  361.         val = id >> 4;
  362.         id  &= 0x0f;
  363.         do {
  364.             *bitlength++ = val;
  365.             charset--;
  366.             } while (--id >= 0);
  367.         } while (charset > 0);
  368. }
  369.  
  370.  
  371. //****************************************************************************
  372.  
  373. int write_cnt2(register uchar *bitlength,int charset,uint test)
  374. {
  375.     if (!test)
  376.         return charset/2;
  377.  
  378.     do {
  379.         bit_write(*bitlength<<(HIGH_BIT-4),4);    // 4 Bit
  380.         bitlength++;
  381.         } while (--charset);
  382. }
  383. int read_cnt2(register uchar *bitlength,int charset)
  384. {
  385.     do {
  386.         *bitlength++ = bit_read(4);        // 4 Bit
  387.         } while (--charset);
  388. }
  389.  
  390. //****************************************************************************
  391.  
  392. int write_cnt3(register uchar *bitlength,int charset,uint test)
  393. {
  394.     register int needed,loop,bitval;
  395.  
  396.     for (bitval = 0,loop=0,needed=0; loop < charset;loop++,bitlength++)
  397.         {
  398.         while (bitval > bitlength[0])
  399.             {
  400.             bitval--,needed+=2;
  401.             if (test)
  402.                 bit_write(0x01 << (HIGH_BIT-2),2);
  403.             }
  404.         while (bitval < bitlength[0])
  405.             {
  406.             bitval++,needed+=2;
  407.             if (test)
  408.                 bit_write(0x00 << (HIGH_BIT-2),2);
  409.             }
  410.         if (test)
  411.             bit_write(0x1 << (HIGH_BIT-1),1);
  412.         needed++;
  413.         }
  414.     return (needed+7)/8;
  415. }
  416. int read_cnt3(register uchar *bitlength,int charset)
  417. {
  418.     register int needed,loop,bitval;
  419.  
  420.     for (bitval = 0; --charset >= 0;)
  421.         {
  422.         while (bit_read(1) == 0)
  423.             if (bit_read(1))
  424.                 bitval--;
  425.             else
  426.                 bitval++;
  427.         *bitlength++ = bitval;
  428.         }
  429. }
  430. //****************************************************************************
  431.  
  432. int write_cnt4(register uchar *bitlength,int charset,uint test)
  433. {
  434.     register int needed,bitval;
  435.  
  436.     for (bitval = 0,needed=0; --charset >= 0;bitlength++)
  437.         {
  438.         if (bitval != bitlength[0])
  439.             {
  440.             bitval = bitlength[0],needed+=5;
  441.             if (test)
  442.                 {
  443.                 bit_write(1 << (HIGH_BIT-1),1);
  444.                 bit_write( bitlength[0] << (HIGH_BIT-4),4);
  445.                 }
  446.             }
  447.         else
  448.             {
  449.             if (test)
  450.                 bit_write(0 << (HIGH_BIT-1),1);
  451.             needed++;
  452.             }
  453.         }
  454.     return (needed+7)/8;
  455. }
  456.  
  457. int read_cnt4(register uchar *bitlength,int charset)
  458. {
  459.     register int bitval;
  460.  
  461.     for (bitval = 0; --charset >= 0;bitlength++)
  462.         {
  463.         if (bit_read(1))
  464.             bitval = bit_read(4);
  465.         *bitlength = bitval;
  466.         }
  467. }
  468.  
  469. //****************************************************************************
  470.  
  471. typedef int (*wrf)(register uchar *,int,uint);
  472. typedef int (*rdf)(register uchar *,int);
  473.  
  474. wrf write_fun[] = { write_cnt0,write_cnt1,write_cnt2,write_cnt3,write_cnt4};
  475. rdf read_fun[]  = {  read_cnt0, read_cnt1, read_cnt2, read_cnt3, read_cnt4};
  476.  
  477.  
  478. test_wr_cnt(uchar *bitlength,int charset)
  479. {
  480.     uint needed = 0xffff,len,method;
  481.  
  482.     bit_write_method = 1;
  483.  
  484.     for (method = 1;method < LENGTH(write_fun);method++) 
  485.         {
  486.         len = (*write_fun[method])(bitlength,charset,FALSE);
  487.         if (len < needed)
  488.             bit_write_method = method,needed = len;
  489.  
  490.         }
  491.  
  492.     return needed;
  493. }
  494.  
  495. //****************************************************************************
  496.  
  497.  
  498.  
  499.  
  500. #define LITLEN 256        // characterset for literal characters
  501. #define LENLEN 16        // characterset for length 0..15
  502. #define INDLEN (4096 >> INDSHIFT)    // characterset for index = (0..4096) >> 4
  503. #define MASLEN 256        // characterset for packmask
  504. #define EXTLEN 256        // characterset for extended length
  505. #define INDSHIFT 4
  506. #define INDMASK  0x0f
  507.  
  508. #define LIT_MAX 12        // MAXIMUM needed bits for each charset
  509. #define IND_MAX 11
  510. #define LEN_MAX 7
  511. #define MAS_MAX 11
  512. #define EXT_MAX 11
  513.  
  514. #define LIT_FLAG 0
  515. #define IND_FLAG 3
  516. #define LEN_FLAG 6
  517. #define MAS_FLAG 9
  518. #define EXT_FLAG 12
  519.  
  520.  
  521. uint do_huff    = 0;    
  522. uint huff_saved = 0;
  523.  
  524.  
  525.  
  526. hs_count(huff_tab *lit_tab,
  527.         huff_tab *len_tab,
  528.         huff_tab *ind_tab,
  529.         huff_tab *mas_tab,
  530.         huff_tab *ext_tab,uchar far *pbuffer,uint packlen)
  531. {
  532.     register int uloop;
  533.     register uchar packmask;
  534.     int length;unsigned index;
  535.  
  536.     for (uloop = 1;packlen > 0;packmask <<= 1)
  537.         {
  538.         if (--uloop == 0)
  539.             {
  540.             packmask    = *pbuffer++,packlen--;
  541.             mas_tab[packmask].count++;
  542.             uloop = 8;
  543.             }
  544.         if ((packmask & 0x80) == 0)                /* this byte is literally */
  545.             {
  546.             lit_tab[*pbuffer++].count++;
  547.             packlen--;
  548.             }
  549.         else
  550.             {                                    /* next 2 bytes coded     */
  551.             index = *(int far *)pbuffer;        /* 4 bit length              */
  552.             length = (index >> 12);
  553.             ind_tab[(index & SENDLEN) >> INDSHIFT].count++;
  554.             len_tab[length].count++;
  555.             if (length == MAXCODELENGTH)        /* length > 18              */
  556.                 {                                /* use next byte for length*/
  557.                 ext_tab[pbuffer[2]].count++;
  558.                 pbuffer += 3;
  559.                 packlen -= 3;
  560.                 }
  561.             else {
  562.                 packlen -= 2;
  563.                 pbuffer += 2;
  564.                 }
  565.             }            
  566.         }
  567. }
  568.  
  569. #define HWRITE(x,tab) bit_write(tab[x].bitcode,tab[x].bitcnt)
  570.  
  571. hs_write(huff_code *lit_code,
  572.         huff_code *len_code,
  573.         huff_code *ind_code,
  574.         huff_code *mas_code,
  575.         huff_code *ext_code,uchar far *pbuffer,uint packlen)
  576. {
  577.     register int uloop;
  578.     register uchar packmask;
  579.     int length;unsigned index;
  580.  
  581.     for (uloop = 1;packlen > 0;packmask <<= 1)
  582.         {
  583.         if (--uloop == 0)
  584.             {
  585.             packmask    = *pbuffer++,packlen--;
  586.             HWRITE(packmask,mas_code);
  587.             uloop = 8;
  588.             }
  589.         if ((packmask & 0x80) == 0)                /* this byte is literally */
  590.             {
  591.             HWRITE(*pbuffer,lit_code);
  592.             pbuffer++;
  593.             packlen--;
  594.             }
  595.         else
  596.             {                                    /* next 2 bytes coded     */
  597.             index = *(int far *)pbuffer;        /* 4 bit length              */
  598.             length = (index >> 12);
  599.  
  600.             HWRITE(length,len_code);
  601.             index &= SENDLEN;
  602.             HWRITE(index >> INDSHIFT,ind_code);
  603.             bit_write((index&INDMASK) << (HIGH_BIT-INDSHIFT),INDSHIFT);
  604.  
  605.             if (length == MAXCODELENGTH)        /* length > 18              */
  606.                 {                                /* use next byte for length*/
  607.                 HWRITE(pbuffer[2],ext_code);
  608.                 pbuffer += 3;
  609.                 packlen -= 3;
  610.                 }
  611.             else {
  612.                 pbuffer += 2;
  613.                 packlen -= 2;
  614.                 }
  615.             }            
  616.         }
  617. }
  618.  
  619. unsigned  summup(register huff_tab *tab,uint charset)
  620. {
  621.     uint sum = 0;
  622.     do {
  623.         sum += tab->count;
  624.         tab++;
  625.         } while (--charset);
  626.     return sum;
  627. }
  628.  
  629.  
  630. //
  631. // check whether this code should be huffed
  632. // do some (de)allocation at the same time
  633. //
  634. huff_code *hs_wr_code(huff_tab *tab,int charset,int maxbit,uint do_flag)
  635. {
  636.     uchar *bitlength;
  637.     huff_code *code;
  638.     uint   huff_len;
  639.     int    needed,loop;
  640.     uint   flatlen = ln2(charset);                    // number of bits in charset
  641.     uint maxlen = (uint)((long)summup(tab,charset) * flatlen / 8);
  642.                                                     // used if stored flat
  643.  
  644.     bitlength = ck_alloc(charset);
  645.  
  646.     huff_len = gen_length(bitlength,tab,charset,maxbit);
  647.  
  648.     needed =   test_wr_cnt(bitlength,charset);
  649.  
  650.     code = ck_alloc(charset*sizeof(huff_code));
  651.  
  652.     if (needed + huff_len < maxlen)
  653.         {
  654.         huff_saved += maxlen - (needed + huff_len);
  655.         do_huff |= bit_write_method << do_flag;
  656.         (*write_fun[bit_write_method])(bitlength,charset,TRUE);
  657.         }
  658.     else
  659.         {
  660.         memset(bitlength,flatlen,charset);            // generate flat characterset
  661.         }
  662.  
  663.     gen_code(code,bitlength,charset);
  664.  
  665.     free(bitlength);
  666.     free(tab);
  667.     return code;
  668. }
  669.  
  670. hs_pack(uchar far *hbuffer,uint plen,uchar far *pbuffer,uint length)
  671. {
  672.     huff_tab *lit_tab,*len_tab,*ind_tab,*mas_tab,*ext_tab;
  673.     huff_code *lit_code,*len_code,*ind_code,*mas_code,*ext_code;
  674.     uint   huff_len;
  675.     register int loop;
  676.  
  677.     memset(hbuffer,0,plen);
  678.  
  679.     lit_tab  = ck_alloc(LITLEN*2*sizeof(huff_tab));
  680.     ind_tab  = ck_alloc(INDLEN*2*sizeof(huff_tab));
  681.     len_tab  = ck_alloc(LENLEN*2*sizeof(huff_tab));
  682.     mas_tab  = ck_alloc(MASLEN*2*sizeof(huff_tab));
  683.     ext_tab  = ck_alloc(EXTLEN*2*sizeof(huff_tab));
  684.  
  685.     hs_count(lit_tab,len_tab,ind_tab,mas_tab,ext_tab,pbuffer,length);
  686.  
  687.     do_huff    = 0;
  688.     huff_saved = 0;
  689.  
  690.     bit_init(hbuffer+4);
  691.  
  692.     lit_code = hs_wr_code(lit_tab,LITLEN,LIT_MAX,LIT_FLAG);
  693.     ind_code = hs_wr_code(ind_tab,INDLEN,IND_MAX,IND_FLAG);
  694.     len_code = hs_wr_code(len_tab,LENLEN,LEN_MAX,LEN_FLAG);
  695.     mas_code = hs_wr_code(mas_tab,MASLEN,MAS_MAX,MAS_FLAG);
  696.     ext_code = hs_wr_code(ext_tab,EXTLEN,EXT_MAX,EXT_FLAG);
  697.  
  698.     if (do_huff == 0 )                        // there is nothing to do
  699.         {    
  700.         return 0xffff;
  701.         }
  702.  
  703.     if (length - huff_saved + 6 >= plen)    // or its not worth the effort    
  704.         {                                
  705.         return 0xffff;
  706.         }
  707.  
  708.  
  709.     ((short far *)hbuffer)[0] = do_huff;
  710.     ((short far *)hbuffer)[1] = length;
  711.  
  712.     hs_write(lit_code,len_code,ind_code,mas_code,ext_code,pbuffer,length);
  713.  
  714.     free(lit_code);
  715.     free(ind_code);
  716.     free(len_code);
  717.     free(mas_code);
  718.     free(ext_code);
  719.  
  720.     bit_flush();
  721.  
  722.     return (uchar far *)bit_ptr - (uchar far *)pbuffer;
  723. }
  724.  
  725.  
  726. huff_icode *hs_rd_code(int charset,int maxbit,uint flatlen,int do_flag)
  727. {
  728.     uchar *bitlength;
  729.     huff_code *code;
  730.     huff_icode *icode;
  731.     register int loop;
  732.  
  733.     bitlength = ck_alloc(charset);
  734.  
  735.     (*read_fun[(do_huff >> do_flag) & 0x07])(bitlength,charset);
  736.  
  737.     code = ck_alloc(charset*sizeof(huff_code));
  738.     gen_code(code,bitlength,charset);
  739.     free(bitlength);
  740.  
  741.     icode = ck_alloc((1<<maxbit)*sizeof(huff_icode));
  742.     gen_invtab(icode,code,charset,maxbit);
  743.     free(code);
  744.     return icode;
  745. }
  746.  
  747. hs_unpack(uchar far *ubuffer,uchar far *hbuffer,uint packlen)
  748. {
  749.     huff_icode *lit_icode,*len_icode,*ind_icode,*mas_icode,*ext_icode;
  750.     register int uloop;
  751.     register uchar packmask;
  752.     int length;unsigned index;
  753.     uchar far *sbuffer = ubuffer;
  754.  
  755.     do_huff = ((short far *)hbuffer)[0];
  756.     packlen = ((short far *)hbuffer)[1];
  757.  
  758.     bit_init(hbuffer+4);
  759.  
  760.     lit_icode = hs_rd_code(LITLEN,LIT_MAX,8,LIT_FLAG);
  761.     ind_icode = hs_rd_code(INDLEN,IND_MAX,8,IND_FLAG);
  762.     len_icode = hs_rd_code(LENLEN,LEN_MAX,4,LEN_FLAG);
  763.     mas_icode = hs_rd_code(MASLEN,MAS_MAX,8,MAS_FLAG);
  764.     ext_icode = hs_rd_code(EXTLEN,EXT_MAX,8,EXT_FLAG);
  765.  
  766.     for (uloop = 1;packlen > 0;packmask <<= 1)
  767.         {
  768.         if (--uloop == 0)
  769.             {
  770.             packmask    = huff_read(mas_icode,MAS_MAX),packlen--;
  771.             uloop = 8;
  772.             }
  773.         if ((packmask & 0x80) == 0)                /* this byte is literally */
  774.             {
  775.             *ubuffer++ = huff_read(lit_icode,LIT_MAX),packlen--;
  776.             }
  777.         else
  778.             {                                    /* next 2 bytes icoded     */
  779.             length = huff_read(len_icode,LEN_MAX)+MIN_LENGTH;
  780.             index  = huff_read(ind_icode,IND_MAX) << INDSHIFT;
  781.             index += bit_read(INDSHIFT);
  782.  
  783.             if (length == MAXCODELENGTH+MIN_LENGTH)    /* length > 18              */
  784.                 {                                /* use next byte for length*/
  785.                 length  = huff_read(ext_icode,EXT_MAX);        /* icode is 3 bytes          */
  786.                 packlen -= 3;
  787.                 }
  788.             else {
  789.                 packlen -= 2;
  790.                 }
  791.                                     /* copy BYTEWISE with OVERWRITE */
  792.             if (index == 1)            // memcpy will not work as it copies WORDS
  793.                 memset(ubuffer,*(ubuffer-1),length);
  794.             else
  795.                 memcpy(ubuffer,ubuffer-index,length);
  796.  
  797.             ubuffer += length;
  798.             }            
  799.         }
  800.  
  801.     free(lit_icode);
  802.     free(ind_icode);
  803.     free(len_icode);
  804.     free(mas_icode);
  805.     free(ext_icode);
  806.  
  807.     return ubuffer-sbuffer;
  808. }
  809.  
  810.  
  811. #ifdef TEST 
  812.  
  813. /**
  814. **/
  815.  
  816.  
  817.  
  818. #define BSIZE   4096
  819. #define CHARSET 256
  820.  
  821. unsigned char buffer[BSIZE];
  822. unsigned char pbuffer[BSIZE];
  823. unsigned char ubuffer[BSIZE];
  824.  
  825.  
  826. main(int argc,char *argv[])
  827. {
  828.     int  fd;
  829.     uint loop,rd,code;
  830.     uint hufflen;
  831.     long inlen = 0,outlen = 0;
  832.     long time,ptime=0,utime=0;
  833.     
  834.     if ((fd = open(argv[1],O_RDONLY|O_BINARY)) < 0)
  835.         return 1;
  836.  
  837.     tx_init();
  838.     
  839.     
  840.  
  841.     while ((rd = read(fd,buffer,BSIZE)) > 0)
  842.         {
  843.         inlen += rd;
  844.  
  845.         mikro_diff();
  846.         hufflen = huff_pack(pbuffer,BSIZE,buffer,rd,CHARSET,12);
  847.         ptime += mikro_diff();
  848.         
  849. //        printf("%5d --> %5d\n",rd,hufflen);
  850.         if (hufflen == 0xffff)    
  851.             {
  852.             outlen += rd;
  853.             continue;
  854.             }
  855.         outlen += hufflen;
  856.  
  857.         memset(pbuffer+hufflen,0xaa,3);
  858.  
  859.         mikro_diff();
  860.         huff_unpack(ubuffer,pbuffer,rd,CHARSET,12);
  861.         utime += mikro_diff();
  862.  
  863.         for (loop = 0; loop < rd; loop++)
  864.             if (buffer[loop] != ubuffer[loop])
  865.                 {
  866.                 char b[48];
  867.                 printf("differenz at %04x\n",loop);
  868.                 memcpy(b,buffer+loop-16,48);
  869.                 hexdn(b,48);
  870.                 printf("\n");
  871.                 memcpy(b,ubuffer+loop-16,48);
  872.                 hexdn (b,48);
  873.                 exit(1);
  874.                 }
  875.  
  876.         }
  877.  
  878.     printf("inlen %5ld --> outlen %5ld ptime %5ld utime %5ld",inlen,outlen,ptime,utime);
  879.             
  880.     printf(" pack %5ld unpackc %5ld\n",
  881.             inlen*1000/ptime,
  882.             inlen*1000/utime
  883.             );
  884.  
  885.     exit(0);
  886. }
  887. #endif
  888.